#include <iostream>
#include <BinaryTree.hpp>

using namespace std;

class Solution
{
public:
    int maxPathSum(TreeNode *root)
    {
        int maxSum = INT_MIN;
        dps(root, maxSum);
        return maxSum;
    }

    int dps(TreeNode *root, int &maxSum)
    {
        int leftMax = INT_MIN, rightMax = INT_MIN;
        if (root->left)
        {
            leftMax = dps(root->left, maxSum);
        }
        if (root->right)
        {
            rightMax = dps(root->right, maxSum);
        }
        int max = std::max(std::max(leftMax, rightMax), 0) + root->val;
        maxSum = std::max(maxSum, max);
        if (root->left != nullptr && root->right != nullptr)
            maxSum = std::max(maxSum, leftMax + rightMax + root->val);
        return max;
    }
};
int main()
{
    cout << "Code124" << endl;
    Solution s;
    // TreeNode *root = CreatTree("[-10,9,20,null,null,15,7]", "null");
    TreeNode *root = CreatTree("[1,2,3]", "null");
    cout << s.maxPathSum(root) << endl;
    return 0;
}